package 动态规划.背包And分组And切割问题系列;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/1/29 15:56
 */
public class lc2551珠子放入背包 {
    /*
    翻译题目：相邻两个元素组成一对儿，分别取k对儿最大值和k对儿最小值，求差值。
     这个题 真的 很抽象!
     解法: 枚举 每一个 分割点!
     分割点,左右的 value 是要被全部  计算的
     这一点 很关键!(如果 不太理解的话, 可以 看 灵神的 视频讲解!)
     */
    // 下面 给出 arigonte 的写法

    public long putMarbles(int[] weights, int k) {
        long sum[] = new long[weights.length - 1], result = 0;
        // 统计 相同 元素的 和, 也就是 枚举 所有的 分割结果的
        for (int i = 0; i < sum.length; i++) {
            sum[i] = weights[i] + weights[i + 1];
        }
        Arrays.sort(sum);
        for (int i = 1; i < k; i++) {
            result += sum[sum.length - i] - sum[i - 1];
        }
        return result;
    }


    /*
     写一个 动态规划 版本的
     这个 动态规划 , 还是挺有意思的!
     f(index,k,true) 表示 求得 是 最大分数
     f(index,k,false) 表示求 的的 是最小分数
     两种分数 没法 一次 性求出来, 所以 有时候 需要把 问题 拆分
     进行 动态规划, 这个 时候想一想 做成云的  , 咖啡机 洗咖啡 的那道题目(也是 对问题进行拆解)
     其实 这是 两个 动态规划,  ** 最大分数 **  and ** 最小分数 **
     =============  并且内层的 for循环 (枚举行为) 应该是可以省掉的,(斜率优化!)
     */

    public static int recursion(int index,int k,boolean flag,int nums[],int dp[][]){
        // 长时间  不写, 这种 basecase ,就有点生疏了!
        if(index == nums.length && k == 0) {
            return 0;
        }
        // 下面这个 basecase 就是 , 对 无效的 划分, 进行返回一个 对结果值没影响的 一个值!
        // 返回的这个值 还是,很有讲究的!
        if(index == nums.length || k == 0){
            return flag ? Integer.MIN_VALUE / 2 : Integer.MAX_VALUE / 2;
        }
        if(dp[index][k] != 0){
            return dp[index][k];
        }
        // 这样写 真的 是 想多了, 如果 index != len  k 还有剩余 的话, 说明当前的分组策略是 无效的, 直接跳过就行了!
//        if(k == 0){
//            return nums[index] + nums[nums.length - 1];
//        }
        int ans = flag ? 0 : Integer.MAX_VALUE / 2;
        //       i <= nums.length - k 是为了确保, 每个 背包至少 有一个 珠子!(题目 要求)
        for(int i = index;i <= nums.length - k;i++){
            if(flag){
                ans = Math.max(ans,recursion(i + 1,k - 1,flag,nums,dp) + nums[index] + nums[i]);
            }
            else{
                ans = Math.min(ans,recursion(i + 1,k - 1,flag,nums,dp) + nums[index] + nums[i]);
            }
        }
        return dp[index][k] = ans;
    }
    /*
     改个 记忆化 搜索吧
     最终版本的 dp 就不改了, 其实都是一样的
     通过: 93/103
     */
    public static int solution(int nums[],int k){
        int dp[][] = new int[nums.length + 1][k + 1];
        int dp1[][] = new int[nums.length + 1][k + 1];
//        int max = recursion(0,k,true,nums,dp);

        return recursion(0,k,true,nums,dp) - recursion(0,k,false,nums,dp1);
    }
    public static void main(String[] args) {
        int nums[]  = {1,3,5,1};
        int k = 2;
        System.out.println(solution(nums,k));
    }

    /*
    class Solution {
private:
    long long bagProblem(vector<int>& weights, vector<long long>& dp, bool flag) {
        int bagWeight = dp.size() - 1;
        for (int i = 1; i < weights.size(); i++) {
            for (int j = bagWeight; j >= 1; j--) {
                if (flag) dp[j] = max(dp[j], dp[j - 1] + weights[i] + weights[i - 1]);
                else dp[j] = min(dp[j], dp[j - 1] + weights[i] + weights[i - 1]);
            }
        }
        return dp[bagWeight];
    }
public:
    long long putMarbles(vector<int>& weights, int k) {
        vector<long long> dp(k, 0);
        for (int i = 1; i < k; i++) dp[i] = INT_MIN;
        long long maxScore = bagProblem(weights, dp, true);
        for (int i = 1; i < k; i++) dp[i] = INT_MAX;
        long long minScore = bagProblem(weights, dp, false);
        return maxScore - minScore;
    }
};

    这个采用的是 01 背包的 解法, 居然 是正确的 !(算法是正确的, 超时!)
    但是 我感觉有点巧合的存在!
    f(i,k) 表示的 含义: 从 i ~ len ,放入 k个 背包(每个背包至少 一个 珠子) 的最大(小)分数
    - 如果 把 i 归入 k 背包中的 话
    调用 f(i + 1,k) : 背包不变, 继续 向下个 珠子, 做抉择!
    - 如果 i 号珠子 ,归入当前 背包, 并且 i + 1 开始 放入 k - 1 背包中
    f(i + 1,k - 1) + weight[i] + weight[i + 1]

   这种考虑 就有问题, 我感觉只不过是 ,正确的 代码 刚好 是 求相邻的 和,
   与这种 碰巧了吧
     */
}
